package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;
import cn.pugle.oj.catalog.Greedy;

/**
 * O(n)
 * 思路: 整个序列nums中, 从左到右, 如果某一段的sum是负数(比如nums[3-5]加和为负),
 * 那么最大sum的子串一定不跨过这个子串, 在此切一下, 重新累计.
 * <p>
 * 没用DP, 但是和高赞的dp方案如此像 LC53_2
 * <p>
 * 和这个也很像
 * https://leetcode.com/problems/maximum-subarray/discuss/20211/Accepted-O(n)-solution-in-java
 * <p>
 * 分治法解这个题挺呆的
 * https://leetcode.com/problems/maximum-subarray/discuss/20452/C%2B%2B-DP-and-Divide-and-Conquer
 *
 * @author tzp
 * @since 2020/9/17
 */
public class LC53_1 implements DynamicProblem, Greedy {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int end = 0, max = nums[0], currentMax = 0;
        while (end < nums.length) {
            currentMax += nums[end];
            max = Math.max(max, currentMax);
            if (currentMax <= 0) {
                currentMax = 0;
            }
            end++;
        }
        return max;
    }

    public static void main(String[] args) {
        System.out.println(new LC53_1().maxSubArray(new int[]{1, 2, 3, 4}));
        System.out.println(new LC53_1().maxSubArray(new int[]{1, -2, 100, -4}));
        System.out.println(new LC53_1().maxSubArray(new int[]{5, -2, 100, -4}));
        System.out.println(new LC53_1().maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
    }
}
